package leetcode.dp;

/**
 给你一个 只包含正整数 的 非空 数组 nums 。
 请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 */
public class CanPartition416 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%2==1)
            return  false;
        //dp[i][j] 表示  nums的前i(索引)个能否达到j
        boolean[][]dp = new boolean[nums.length][sum/2 + 1];
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }

        for (int i = 0; i <= sum/2; i++) {
            if(nums[0]==i)
                dp[0][i] = true;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= sum/2; j++) {
                if(j-nums[i]>=0)//用nums[i]
                  dp[i][j] = dp[i-1][j-nums[i]];
                //         不用nums[i]
                dp[i][j] = dp[i-1][j] || dp[i][j] ;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= sum/2; j++) {
                System.out.print(dp[i][j]+"\t");

            }
            System.out.println();
        }

        return dp[nums.length-1][sum/2];
    }

    public static void main(String[] args) {
        System.out.println(new CanPartition416().canPartition(new int[]{2,2,3,5}));
    }
}